// 2025/3/4
// https://leetcode.cn/problems/merge-intervals/description/?envType=study-plan-v2&envId=top-100-liked
// 合并区间

class Solution {
    public:
        vector<vector<int>> merge(vector<vector<int>>& intervals) {
            vector<int> diff(20002, 0);
            for(auto& range : intervals)
            {
                ++diff[range[0] * 2];
                --diff[range[1] * 2 + 1];
            }
    
            int left = 0, right = 0;
            vector<vector<int>> ans;
            for(right = 1; right < 20002; right++)
            {
                diff[right] += diff[right - 1];
                if(diff[right] == 0 && diff[right - 1] > 0)
                {
                    while(diff[left] == 0) left++;
                    ans.push_back({left / 2, (right - 1) / 2});
                    left = right;
                }
            }
            return ans;
        }
    };